/*
OpenMVL Matrix Vector Library
Copyright (c) 2009 FluidInteractive (R)
 
This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising
from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:
 
1. The origin of this software must not be misrepresented; you must
not claim that you wrote the original software. If you use this
software in a product, an acknowledgment in the product documentation
would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must
not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
 
Written by: Nicola Candussi <nicola@fluidinteractive.com>
*/

//layout_trans.hpp

#ifndef MVL_LAYOUT_TRANS_HPP
#define MVL_LAYOUT_TRANS_HPP

#include "layout.hpp"

namespace mvl {

namespace layout {

//trans entries
template<typename I, typename J, typename Tag, typename Src>
struct trans_sparse_entry {
    typedef Tag                 tag;           //type of entry
    typedef I                   i;
    typedef J                   j;
    typedef Src                 src;    //refers to the entry in the source layout
    typedef trans_sparse_entry  type;
};

//transpose a layout
template<typename Tag> struct layout_trans_impl;

template<typename Layout>
struct layout_trans: layout_trans_impl<typename Layout::tag>::template apply<Layout> { };

//implementation for dense layout
template<>
struct layout_trans_impl<dense_layout_tag> 
{
    template<typename L>
    struct apply : dense_layout<L::Cols::value, L::Rows::value, typename L::order> { };
};

//
struct transpose_entry {
    template<typename Entry>
    struct apply : trans_sparse_entry<typename Entry::j, typename Entry::i, typename Entry::tag, Entry> { };
};

//transpose of a sparse layout
template<typename L, 
         typename TransposeEntry = transpose_entry,
         typename NewRows = typename L::Cols,
         typename NewCols = typename L::Rows,
         typename NewOrder = typename L::order>
struct layout_sparse_trans {

    typedef L layout_t;
    typedef typename layout_t::order order;
    typedef typename layout_t::entries entries;

    template<typename It, typename Pos1>
    struct it_state {
        typedef It          it;     
        typedef Pos1        pos1;   
        typedef it_state    type;
    };

    struct iterator_back_inserter {
        template<typename State, typename It>
        struct apply : meta::push_back<
            State, 
            it_state<
                typename meta::begin<typename meta::deref<It>::type>::type,
                typename meta::distance<
                    typename meta::begin<entries>::type,
                    It
                >::type
            >
        > { };
    };

    //gather all begin of the row iterators
    typedef typename meta::iter_fold<
        typename meta::begin<entries>::type,
        typename meta::end<entries>::type,
        meta::vector<>,
        iterator_back_inserter
    >::type it_begin_vector;

    //do conversion
    template<typename ItState, typename Data, typename Pos2, typename Condition>
    struct loop_state {
        typedef ItState     it_state_vector;
        typedef Data        data;
        typedef Pos2        pos2;
        typedef Condition   condition;
        typedef loop_state  type;
    };

    struct back_inserter {

        //if the row iterator is not at the end, we insert the entry it contains into the new layout and
        template<typename NotEnd, typename State, typename It> struct apply_helper;
        //case of it != end
        template<typename State, typename It> struct apply_helper<meta::bool_<true>, State, It> {
            typedef typename meta::deref<It>::type current_it_state;
            typedef typename current_it_state::it it;       
            typedef typename current_it_state::pos1 pos1;  
            typedef typename meta::deref<it>::type entry;
            typedef typename get2<typename entry::i, typename entry::j, order>::type entry_pos2;  //column of the entry in the transposed 
            typedef typename meta::equal_to<entry_pos2, typename State::pos2>::type same_pos2;

            typedef typename TransposeEntry::template apply<entry>::type transposed_entry;

            typedef typename meta::eval_if<
                same_pos2,
                meta::push_back<
                    typename meta::at<
                        typename State::data,
                        typename State::pos2  
                    >::type,
                    transposed_entry
                >,
                meta::identity<meta::none>
            >::type new_column;

            typedef typename meta::push_back<
                typename State::it_state_vector,
                it_state<
                    typename meta::eval_if<
                        same_pos2,
                        meta::next<it>,
                        meta::identity<it>
                    >::type,
                    pos1
                >
            >::type new_it_state_vector;

            typedef typename loop_state<
                new_it_state_vector,
                typename meta::eval_if<
                    same_pos2,
                    meta::replace_element<
                        typename State::data,
                        typename State::pos2,
                        new_column
                    >,
                    meta::identity<typename State::data>
                >::type,
                typename State::pos2,
                typename meta::not_equal_to<
                    typename meta::size<new_it_state_vector>::type,
                    meta::int_<0>
                >::type
            >::type type;
        };

        //case of it == end
        template<typename State, typename It> struct apply_helper<meta::bool_<false>, State, It> {
            typedef typename loop_state<
                typename State::it_state_vector,
                typename State::data,
                typename State::pos2,
                typename meta::not_equal_to<
                    typename meta::size<typename State::it_state_vector>::type,
                    meta::int_<0>
                >::type
            >::type type;
        };
 
        template<typename State, typename It>
        struct apply {
            typedef typename meta::deref<It>::type current_it_state;
            typedef typename current_it_state::it it;       //row iterator
            typedef typename current_it_state::pos1 pos1;  //row index

            //find the end of the row
            typedef typename meta::end<
                typename meta::at<
                    entries,
                    pos1
                >::type
            >::type end;

            typedef typename apply_helper<
                typename meta::not_equal_to<it, end>::type,
                State,
                It
            >::type type;
        };
    };

    struct update {
        template<typename State> 
        struct apply {
            typedef typename meta::iter_fold<
                typename meta::begin<typename State::it_state_vector>::type,
                typename meta::end<typename State::it_state_vector>::type,
                loop_state<
                    meta::vector<>,
                    typename State::data,
                    typename State::pos2,
                    typename State::condition
                >,
                back_inserter
            >::type new_state;

            typedef loop_state<
                typename new_state::it_state_vector,
                typename new_state::data,
                typename meta::next<typename State::pos2>::type,
                typename new_state::condition
            > type;
        };
    };

    typedef typename meta::while_<
        loop_state<
            it_begin_vector,
            meta::tvector<
                meta::vector<>,
                typename get2<typename L::Rows, typename L::Cols, order>::type
            >,
            meta::int_<0>,
            typename meta::not_equal_to<
                typename meta::begin<it_begin_vector>::type,
                typename meta::end<it_begin_vector>::type
            >::type
        >,
        update
    >::type::data result;
    typedef typename sparse_layout<NewRows::value, NewCols::value, NewOrder, result, L::Size::value>::type type;
};

//implementation for sparse layout
template<>
struct layout_trans_impl<sparse_layout_tag> 
{
    template<typename L>
    struct apply : layout_sparse_trans<L, transpose_entry> { };
};

} //namespace layout

} //namespace mvl


#endif
